#include <iostream>
#include <unordered_set>
#include <queue>
#include <string>

using namespace std;

unordered_set<string> s;
const int dir[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

void bfs() {
    queue<string> q;
    q.push("ABCDE*");
    s.insert("ABCDE*");
    while (!q.empty()) {
        string t = q.front();
        q.pop();
        int w = t.find('*');
        int x = w / 3, y = w % 3;
        for (int i = 0; i < 4; ++i) {
            int xx = x + dir[i][0], yy = y + dir[i][1];
            if (xx < 0 || xx > 1 || yy < 0 || yy > 2) continue;
            swap(t[w], t[xx * 3 + yy]);
            if (!s.count(t)) {
                q.push(t);
                s.insert(t);
            }
            swap(t[w], t[xx * 3 + yy]);
        }
    }
}

int main() {
    bfs();
    int n;
    cin >> n;
    while (n--) {
        string e;
        cin >> e;
        if (s.count(e)) cout << 1 << '\n';
        else cout << 0 << '\n';
    }

    return 0;
}